package problem416;

//416.分割等和子集
//https://leetcode.cn/problems/partition-equal-subset-sum/


// class Solution {
//     public boolean canPartition(int[] nums) {
//         int n = nums.length;
//         int sum = 0;
//         for(int i = 0; i<n; i++) {
//             sum += nums[i];
//         }
//         if(sum%2!=0) return false;
//         int m = sum/2;
//         boolean[][] dp = new boolean[n+1][m+1];
        
//         dp[0][0] = true;

//         for(int i = 1; i<=n; i++) {
//             for(int j = 1; j<=m; j++) {
//                 dp[i][j] = dp[i-1][j];
//                 if(j-nums[i-1]>=0 ) dp[i][j] = dp[i][j] || dp[i-1][j-nums[i-1]];
//             }
//         }
//         return dp[n][m];
//     }
// }

/*
dp[i][j]:从前i个数中选, 和正好为j
*/

class Solution {
    public boolean canPartition(int[] nums) {
        int n = nums.length;
        int sum = 0;
        for(int i = 0; i<n; i++) {
            sum += nums[i];
        }
        if(sum%2!=0) return false;
        int m = sum/2;
        boolean[] dp = new boolean[m+1];
        
        dp[0] = true;

        for(int i = 1; i<=n; i++) {
            for(int j = m; j>=nums[i-1]; j--) {
                if(dp[j-nums[i-1]]) dp[j] = true;
            }
        }
        return dp[m];
    }
}